Contains duplicate III

Time: O(NLogK); Space: O(K); medium

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0

Output: True

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2

Output: True

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3

Output: False

Hints:

  1. Time complexity O(n logk) - This will give an indication that sorting is involved for k elements.

  2. Use already existing state to evaluate next state - Like, a set of k sorted numbers are only needed to be tracked. When we are processing the next number in array, then we can utilize the existing sorted state and it is not necessary to sort next overlapping set of k numbers again.

[1]:

import collections

class Solution1(object):
    """
    Time: O(N*T)
    Space: O(MAX(K,T))
    """
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k < 0 or t < 0:
            return False

        window = collections.OrderedDict()

        for n in nums:
            # Make sure window size
            if len(window) > k:
                window.popitem(False)

            bucket = n if not t else n // t
            # At most 2t items.
            for m in (window.get(bucket - 1), window.get(bucket), window.get(bucket + 1)):
                if m is not None and abs(n - m) <= t:
                    return True
            window[bucket] = n

        return False

[2]:

s = Solution1()

nums = [1,2,3,1]
k = 3
t = 0
assert s.containsNearbyAlmostDuplicate(nums, k, t) == True

nums = [1,0,1,1]
k = 1
t = 2
assert s.containsNearbyAlmostDuplicate(nums, k, t) == True

nums = [1,5,9,1,5,9]
k = 2
t = 3
assert s.containsNearbyAlmostDuplicate(nums, k, t) == False